AT5200 [AGC038C] LCMs

i=1nj=i+1nlcm(Ai,Aj)\sum_{i=1}^n\sum_{j=i+1}^n\text{lcm}(A_i,A_j)

i=1nj=1nlcm(Ai,Aj)i=1nAi2\frac{\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(A_i,A_j)-\sum_{i=1}^nA_i}{2}

所以只需要快速求到 i=1nj=1nlcm(Ai,Aj)\sum_{i=1}^n\sum_{j=1}^n lcm(A_i,A_j) 即可 , 其实就是 P3911

下面给一下过程:

cic_i 表示 ii 出现的次数,nn 为最大数字。

i=1nj=1nci×cj×lcm(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j)

i=1nj=1nci×cj×i×jgcd(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times \frac{i \times j}{gcd(i,j)}

k=1ni=1nj=1n[gcd(i,j)=k]ci×cj×i×jk\sum_{k=1}^n\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)=k] c_i \times c_j \times \frac{i \times j}{k}

k=1ni=1nkj=1nk[gcd(i,j)=1]cik×cjk×i×j×k\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} [gcd(i,j)=1] c_{ik} \times c_{jk} \times i \times j \times k

k=1ni=1nkj=1nkdgcd(i,j)μ(d)×cik×cjk×i×j×k\sum_{k=1}^n\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{d|gcd(i,j)}\mu(d) \times c_{ik} \times c_{jk} \times i \times j \times k

k=1nd=1nkμ(d)×d2i=1nkdj=1nkdcikd×cjkd×i×j×k\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \times d^2 \sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{kd} \rfloor} c_{ikd} \times c_{jkd} \times i \times j \times k

k=1nkd=1nμ(d)×d2i=1nkdj=1nkdcikd×cjkd×i×j×k\sum_{k=1}^n\sum_{kd=1}^{n}\mu(d) \times d^2\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{kd} \rfloor} c_{ikd} \times c_{jkd} \times i \times j \times k

T=1nT(dTμ(d)×d)i=1nTj=1nTciT×cjT×i×j\sum_{T=1}^n T(\sum_{d|T}\mu(d) \times d )\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor } \sum_{j=1}^{\lfloor \frac{n}{T} \rfloor} c_{iT} \times c_{jT} \times i \times j

T=1nT(dTμ(d)×d)(i=1nTciT×i)2\sum_{T=1}^n T(\sum_{d|T}\mu(d) \times d ) (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor } c_{iT} \times i)^2

第一个括号预处理,第二个括号直接暴力算。

预处理和查询复杂度均为 Θ(nlnn)\Theta(n \ln n)

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1e6 , Mod = 998244353;
int n , m , Ans , cnt[ MAXN + 5 ];

int k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
    mu[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ k ] = i;
            mu[ i ] = -1;
        }
        for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            if( i % prime[ j ] == 0 ) break;
            mu[ i * prime[ j ] ] = -mu[ i ];
        }
    }
    for( int i = 1 ; i <= MAXN ; i ++ )
        for( int j = i ; j <= MAXN ; j += i )
            f[ j ] = ( f[ j ] + i * mu[ i ] + Mod ) % Mod;
}

int main( ) {
    sieve( );
    scanf("%d",&n);
    for( int i = 1 , x ; i <= n ; i ++ ) {
        scanf("%d",&x) , Ans = ( Ans - x + Mod ) % Mod;
        cnt[ x ] ++ , m = max( m , x );
    }
    n = m;

    for( int i = 1 ; i <= n ; i ++ ) {
        int tmp = 0;
        for( int j = 1 ; j <= n / i ; j ++ )
            tmp = ( tmp + 1ll * cnt[ i * j ] * j % Mod ) % Mod;
        Ans = ( Ans + 1ll * i * f[ i ] % Mod * tmp % Mod * tmp % Mod ) % Mod;
    }

    printf("%d", 1ll * Ans * 499122177 % Mod );
    return 0;
}